package com.mrzhou.study.struct.linked;

/**
 *  约瑟夫问题:
 *      问题介绍: 见 classpath: doc/Java数据结构和算法.pdf 的4.7节
 */
public class Josephu<T> {

    private Node<T> header;
    private int size;

    /**
     * 这里不允许通过设置下标的方式插入, 只能从链表的尾部插入
     */
    public void add(T elem) {
        if(isEmpty()) { // 当只有一个节点的时候就自己指向自己
            Node node = new Node<>(elem, null, null);
            header = node;
            node.pre = node;
            node.next = node;
        } else {
            Node<T> current = this.header;
            while (current.next != this.header) {
                current = current.next;
            }
            Node<T> node = new Node<>(elem, current, this.header);
            current.next = node;
            this.header.pre = node; // 这里需要将header的上一个节点指针修改成
        }
        size++;
    }

    /**
     * 每次取出链表的第m的节点
     */
    public LinkedList<T> get(int m) {
        checkPositionIndex(m);
        LinkedList<T> list = new LinkedList();
        Node<T> current = this.header;
        int loop = 1; // 计数器
        while(!isEmpty()) {
            if(current.next == current) {
                this.header = null;
                list.addLast(current.elem);
                break;
            }
            if(loop == m){ // 当计数器和m相等时, 表示当前节点需从循环链表中剔除, 这里我把节点中的数据头部保存到LinkedList(个人)中
                // 获取即将删除节点的上一个节点和下一节点, 并将删除的数据保存链表中
                list.addLast(current.elem);
                Node<T> preNode = current.pre;
                Node<T> nextNode = current.next;
                // 将上一节点的next改为current.next
                preNode.next = current.next;
                // 将nextNode的pre修改为preNode;
                nextNode.pre = preNode;
                // 将需要删除的节点从链表中断开
                delNode(current);
                current = preNode.next;
                loop = 1;
                continue;
            }
            loop++;
            current = current.next;
        }
        return list;
    }

    public void remove() {

    }

    public static void main(String[] args) {
        Josephu<String> josephu = new Josephu<>();
        for(int i = 0; i < 10 ; i++) {
            josephu.add(String.format("%d", i));
        }
        System.out.printf("顺序打印循环链表中####\n节点的大小: %d\n元素信息: %s\n", josephu.size, josephu);
        System.out.printf("约瑟夫取出的元素顺序为: %s\n", josephu.get(3));
//        System.out.printf("逆序打印循环链表中####\n节点的大小: %d\n元素信息: %s\n", josephu.size, josephu.toLastString());
    }

    private void checkPositionIndex(int index) {
        if(!isPositionIndex(index)) {
            throw new ArrayIndexOutOfBoundsException(String.format("超过循环链表的最大长度, 链表最大索引: %d\t入参索引: %d",  size ,  index));
        }
    }

    private boolean isPositionIndex(int index) {
        return index >= 1 && index <= size;
    }


    public boolean isEmpty() {
        return this.header == null;
    }

    public String toString() {
        StringBuffer sb = new StringBuffer("[");
        if(!isEmpty()) {
            Node current = this.header;
            while(current.next != this.header) {
                sb.append(current.elem).append(", ");
                current = current.next;
            }
            sb.append(current.elem);
        }
        return sb.append("]").toString();
    }

    public String toLastString() {
        StringBuffer sb = new StringBuffer("[");
        if(!isEmpty()) {
            Node<T> current = this.header.pre;
            while(current != this.header && current != null) {
                sb.append(current.elem).append(", ");
                current = current.pre;
            }
            sb.append(current.elem);
        }
        return sb.append("]").toString();
    }

    private void delNode(Node remove) {
        remove.pre = null;
        remove.next = null;
    }

    private class Node<T>{
        T elem;
        Node<T> pre;
        Node<T> next;
        Node() { }
        Node(T elem, Node<T> pre, Node<T> next) {
            this.elem = elem;
            this.pre = pre;
            this.next = next;
        }
    }

}
